import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: LianBao
 * Date: 2024-04-19
 * Time: 17:37
 */
public class Heap {

    public int[] elem;//存储数据的数组
    public int curSize;//当前数据的个数

    public Heap(int[] array) {
        //构造方法,初始化时给elem数组
        elem = new int[10];
        for (int i = 0; i < array.length; i++) {
            elem[i] = array[i];
            curSize++;
        }
    }
    //创建堆(大根堆)
    public void createMaxHeap(int[] array) {
        for (int parent = (array.length - 1 - 1) / 2; parent >= 0; parent--) {
            shiftDownMax(elem, parent, array.length);
        }
    }

    //创建堆(小根堆)
    public void createMinHeap(int[] array) {
        for (int parent = (elem.length - 1 - 1) / 2; parent >= 0; parent--) {
            shiftDownMin(elem, parent, elem.length);
        }
    }

    //向下调整:大根堆
    private void shiftDownMax(int[] array, int parent, int end) {
        int child = (parent * 2) + 1;

        while (child < end) {
            if (child + 1 < end && array[child] < array[child + 1]) {
                child++;
            }
            //child是最大的
            if (array[child] > array[parent]) {
                swap(array, child, parent);
                parent = child;
                child = parent * 2 + 1;
            } else {
                break;//已经是大根堆了,结束循环
            }
        }
    }

    //向下调整:小根堆
    private void shiftDownMin(int[] array, int parent, int end) {
        int child = (parent * 2) + 1;

        while (child < end) {
            if (child + 1 < end && array[child] > array[child + 1]) {
                child++;
            }
            //child是最大的

            if (array[child] < array[parent]) {
                swap(array, child, parent);
                parent = child;
                child = parent * 2 + 1;
            } else {
                break;//已经是小根堆了,结束循环
            }
        }
    }

    /**
     * 插入数据,大根堆
     *
     * @param key
     */
    public void offerMax(int key) {
        if (curSize == elem.length) {
            //扩容
            elem = Arrays.copyOf(elem, elem.length * 2);
        }
        elem[curSize] = key;
        curSize++;
        shiftUpMax(curSize - 1);
    }

    /**
     * 插入数据,小根堆
     *
     * @param key
     */
    public void offerMin(int key) {
        if (curSize == elem.length) {
            //扩容
            elem = Arrays.copyOf(elem, elem.length * 2);
        }
        elem[curSize] = key;
        curSize++;
        shiftUpMin(curSize - 1);
    }

    /**
     * 删除数据,大根堆
     *
     * @return
     */
    public int poolMax() {
        if (isEmpty()) {
            return -1;
        }
        int ret = elem[0];
        swap(elem, 0, curSize - 1);
        curSize--;
        shiftDownMax(elem, 0, curSize);
        return ret;
    }

    /**
     * 删除数据,小根堆
     * @return
     */
    public int poolMin() {
        if (isEmpty()) {
            return -1;
        }
        int ret = elem[0];
        swap(elem, 0, curSize - 1);
        curSize--;
        shiftDownMin(elem, 0, curSize);
        return ret;
    }

    //向上调整,大顶堆
    private void shiftUpMax(int child) {
        int parent = (child - 1) / 2;
        while (parent >= 0) {
            if (elem[child] > elem[parent]) {
                swap(elem, parent, child);
                child = parent;
                parent = (child - 1) / 2;
            } else {
                break;
            }
        }
    }

    //向上调整,大顶堆
    private void shiftUpMin(int child) {
        int parent = (child - 1) / 2;
        while (parent >= 0) {
            if (elem[child] < elem[parent]) {
                swap(elem, parent, child);
                child = parent;
                parent = (child - 1) / 2;
            } else {
                break;
            }
        }
    }

    //交换
    private void swap(int[] arr, int x, int y) {
        int tmp = arr[x];
        arr[x] = arr[y];
        arr[y] = tmp;
    }

    @Override
    public String toString() {
        StringBuilder str = new StringBuilder();
        for (int i = 0; i < curSize; i++) {
            str.append(elem[i]);
            if (i != curSize - 1) {
                str.append(", ");
            }
        }
        return str.toString();
    }

    //判断是否为空
    private boolean isEmpty() {
        return curSize == 0;
    }
}
